﻿using System;
using System.Collections;
using System.Collections.Generic;

namespace exercise.树
{
    public class BinaryTree<E> : IEnumerable<E>
    {
        protected int size;
        protected Node<E> root;

        // 内部类默认是静态的
        protected class Node<E>
        {
            public E element;
            public Node<E> left;
            public Node<E> right;
            public Node<E> parent;

            public Node(E element, Node<E> parent)
            {
                this.element = element;
                this.parent = parent;
            }

            public bool isLeaf()
            {
                return left == null && right == null;
            }
            public bool hasTwoChild()
            {
                return left != null && right != null;
            }
            public bool isLeftChild()
            {
                return parent != null && this == parent.left;
            }
            public bool isRightChild()
            {
                return parent != null && this == parent.right;
            }
        }

        public delegate bool VisitorAction<E>(E element);

        public void levelOrder(VisitorAction<E> visitor)
        {
            if (root == null || visitor == null) return;

            Queue<Node<E>> queue = new Queue<Node<E>>();
            queue.Enqueue(root);

            while (queue.Count > 0)
            {
                Node<E> node = queue.Dequeue();

                if (visitor(node.element))
                    return;

                // 下一层直接入队列
                if (node.left != null)
                {
                    queue.Enqueue(node.left);
                }
                if (node.right != null)
                {
                    queue.Enqueue(node.right);
                }
            }
        }

        public bool isEmpty()
        {
            return size == 0;
        }

        public void clear()
        {
            root = null;
            size = 0;
        }

        protected void elementNotNullCheck(E element)
        {
            if (element == null)
            {
                throw new ArgumentNullException(nameof(element));
            }
        }

        /// <summary>
        /// 判断是否完全二叉树
        /// 1. 左空右有值 不是
        /// 2. 遇到叶子节点或只有左节点，则之后都是叶子结点
        /// </summary>
        /// <param name="node"></param>
        public bool isComplete()
        {
            Queue<Node<E>> queue = new Queue<Node<E>>();
            queue.Enqueue(root);

            bool mustBeLeaf = false;
            while (queue.Count > 0)
            {
                Node<E> node = queue.Dequeue();
                if (mustBeLeaf && !node.isLeaf())
                {
                    return false;
                }

                if (node.left != null)
                {
                    queue.Enqueue(node.left);
                }
                else if (node.right != null)
                {
                    return false;
                }

                if (node.right != null)
                {
                    queue.Enqueue(node.right);
                }
                else
                {
                    mustBeLeaf = true;
                }
            }

            return true;
        }

        /// <summary>
        /// 计算高度
        /// </summary>
        /// <param name="node"></param>
        public int height()
        {
            //迭代方式
            int height = 0;
            int levelSize = 1; //每层的元素数量
            Queue<Node<E>> queue = new Queue<Node<E>>();
            queue.Enqueue(root);

            while (queue.Count > 0)
            {
                Node<E> node = queue.Dequeue();
                levelSize--;

                // 下一层直接入队列
                if (node.left != null)
                {
                    queue.Enqueue(node.left);
                }
                if (node.right != null)
                {
                    queue.Enqueue(node.right);
                }

                if (levelSize == 0)
                {
                    levelSize = queue.Count;
                    height++;
                }
            }

            return height;
            //return height(root);
        }

        //private int height(Node<E> node)
        //{
        //    if (node == null) return 0;
        //    return 1 + Math.Max(height(node.left), height(node.right));
        //}

        /// <summary>
        /// 前序遍历  根节点在最前面
        /// </summary>
        /// <param name="node"></param>
        public void preorderTraversal()
        {
            preorderTraversal(root);
        }

        private void preorderTraversal(Node<E> node)
        {
            if (node == null) return;

            Console.WriteLine(node.element);
            preorderTraversal(node.left);
            preorderTraversal(node.right);
        }

        /// <summary>
        /// 中序遍历 从小到大
        /// </summary>
        /// <param name="node"></param>
        public void inorderTraversal()
        {
            inorderTraversal(root);
        }

        private void inorderTraversal(Node<E> node)
        {
            if (node == null) return;

            //顺序 左中右
            inorderTraversal(node.left);
            Console.WriteLine(node.element);
            inorderTraversal(node.right);
        }

        /// <summary>
        /// 后序遍历  根节点在最后面
        /// </summary>
        /// <param name="node"></param>
        public void postorderTraversal()
        {
            postorderTraversal(root);
        }

        private void postorderTraversal(Node<E> node)
        {
            if (node == null) return;

            postorderTraversal(node.left);
            postorderTraversal(node.right);
            Console.WriteLine(node.element);
        }

        /// <summary>
        /// 层序遍历
        /// </summary>
        /// <param name="node"></param>
        public void levelOrderTraversal()
        {
            if (root == null) return;

            Queue<Node<E>> queue = new Queue<Node<E>>();
            queue.Enqueue(root);

            while (queue.Count > 0)
            {
                Node<E> node = queue.Dequeue();
                Console.WriteLine(node.element);

                // 下一层直接入队列
                if (node.left != null)
                {
                    queue.Enqueue(node.left);
                }
                if (node.right != null)
                {
                    queue.Enqueue(node.right);
                }
            }
        }

        /// <summary>
        /// 前驱节点
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        protected Node<E> predecessor(Node<E> node)
        {
            if (node == null) return null;

            Node<E> p = node.left;
            if (node.left != null)
            {
                // 1. 左节点或左节点的最深右节点
                while (p.right != null)
                {
                    p = p.right;
                }
                return p;
            }

            // 找父节点 如果节点是父节点的右节点，则必然小于，直接结束
            while (node.parent != null && node == node.parent.left)
            {
                node = node.parent;
            }

            return node.parent;
        }
        /// <summary>
        /// 后继节点
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        protected Node<E> successor(Node<E> node)
        {
            if (node == null) return null;

            Node<E> p = node.right;
            if (p != null)
            {
                // 右节点的最深左节点
                while (p.left != null)
                {
                    p = p.left;
                }
                return p;
            }

            // 找父节点，如果节点是父节点的左节点，则父节点是后继
            while (node.parent != null && node == node.parent.right)
            {
                node = node.parent;
            }

            return node.parent;
        }

        /// <summary>
        /// 反转
        /// </summary>
        /// <param name="node"></param>
        public void invertTree()
        {
            invertTree(root);
        }

        private void invertTree(Node<E> node)
        {
            if (node == null) return;

            (node.right, node.left) = (node.left, node.right);
            invertTree(node.left);
            invertTree(node.right);
        }

        /// <summary>
        /// 打印图
        /// </summary>
        public void PrintTree()
        {
            PrintTree(root);
        }

        private void PrintTree(Node<E> root)
        {
            List<List<string>> lines = new List<List<string>>();

            List<Node<E>> level = new List<Node<E>>();
            List<Node<E>> next = new List<Node<E>>();

            level.Add(root);
            int nn = 1;

            int widest = 0;

            while (nn != 0)
            {
                List<string> line = new List<string>();

                nn = 0;

                foreach (Node<E> n in level)
                {
                    if (n == null)
                    {
                        line.Add(null);

                        next.Add(null);
                        next.Add(null);
                    }
                    else
                    {
                        string aa = n.element.ToString();
                        line.Add(aa);
                        if (aa.Length > widest) widest = aa.Length;

                        next.Add(n.left);
                        next.Add(n.right);

                        if (n.left != null) nn++;
                        if (n.right != null) nn++;
                    }
                }

                if (widest % 2 == 1) widest++;

                lines.Add(line);

                List<Node<E>> tmp = level;
                level = next;
                next = tmp;
                next.Clear();
            }

            int perpiece = lines[lines.Count - 1].Count * (widest + 4);
            for (int i = 0; i < lines.Count; i++)
            {
                List<string> line = lines[i];
                int hpw = (int)Math.Floor(perpiece / 2f) - 1;

                if (i > 0)
                {
                    for (int j = 0; j < line.Count; j++)
                    {
                        char c = ' ';
                        if (j % 2 == 1)
                        {
                            if (line[j - 1] != null)
                            {
                                c = (line[j] != null) ? '┴' : '┘';
                            }
                            else
                            {
                                if (j < line.Count && line[j] != null) c = '└';
                            }
                        }
                        Console.Write(c);

                        if (line[j] == null)
                        {
                            for (int k = 0; k < perpiece - 1; k++)
                            {
                                Console.Write(" ");
                            }
                        }
                        else
                        {
                            for (int k = 0; k < hpw; k++)
                            {
                                Console.Write(j % 2 == 0 ? " " : "─");
                            }
                            Console.Write(j % 2 == 0 ? "┌" : "┐");
                            for (int k = 0; k < hpw; k++)
                            {
                                Console.Write(j % 2 == 0 ? "─" : " ");
                            }
                        }
                    }
                    Console.WriteLine();
                }

                for (int j = 0; j < line.Count; j++)
                {
                    string f = line[j];
                    if (f == null) f = "";
                    int gap1 = (int)Math.Ceiling(perpiece / 2f - f.Length / 2f);
                    int gap2 = (int)Math.Floor(perpiece / 2f - f.Length / 2f);

                    for (int k = 0; k < gap1; k++)
                    {
                        Console.Write(" ");
                    }
                    Console.Write(f);
                    for (int k = 0; k < gap2; k++)
                    {
                        Console.Write(" ");
                    }
                }
                Console.WriteLine();

                perpiece /= 2;
            }
        }

        public IEnumerator<E> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }
    }
}